/*
day100
2019.12.6
*/
#include<stdlib.h>

struct TreeNode {
	int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) 
        {
        	struct TreeNode *tem = new TreeNode(val);
			root=tem; 
		}
	
		if(val > root->val)
		{
			if(root->right)
			{
				insertIntoBST(root->right,val);
			}
			else
			{
				struct TreeNode *tem = new TreeNode(val);
				root->right = tem;
			}
		}
		else
		{
			if(root->left)
			{
				insertIntoBST(root->left,val);
			}
			else
			{
				struct TreeNode *tem = new TreeNode(val);
				root->left = tem;
			}
		}
    	
    	return root;
	}
	
	
	
	TreeNode* insertIntoBST2(TreeNode* root, int val) {
		if(!root) 
        {
        	struct TreeNode *tem = new TreeNode(val);
			root=tem; 
			return root;
		}
		
		struct TreeNode *tem = root;
		while(1)
		{
			if(val > tem->val)
			{
				if(tem->right)
				{
					tem=tem->right;
				}
				else
				{
					struct TreeNode *node=new TreeNode(val);
					tem->right=node;
					break; 
				}
			}
			else
			{
				if(tem->left)
				{
					tem=tem->left;
				}
				else
				{
					struct TreeNode *node=new TreeNode(val);
					tem->left=node;
					break;
				}
			}
		}
		
		return root;
	}
};

int main()
{
	
	return 0;
}
